Omega language

An ω-language is a set of infinite-length sequences of symbols.

Contents

Formal definition

Let Σ be a set of symbols (not necessarily finite). Following the standard definition from formal language theory, Σ* is the set of all finite words over Σ. Every finite word has a length, which is, obviously, a natural number. Given a word w of length n, w can be viewed as a function from the set {0,1,...,n-1} → Σ. The infinite words, or ω-words, can likewise be viewed as functions from \mathbb{N} to Σ, with the value at i giving the symbol at position i. The set of all infinite words over Σ is denoted Σω. The set of all finite and infinite words over Σ is sometimes written Σ.

Thus, an ω-language L over Σ is a subset of Σω.

Operations

Some common operations defined on ω-languages are:

Distance between ω-words

The set Σω can be made into a metric space by definition of the metric d:Σω × ΣωR as:

if w and v share any finite prefix, then d(w,v)= inf {2-|x| : x in Σ*, and x in both Pref(w) and Pref(v) }.
otherwise d(w, v)=1

where |x| is interpreted as "the length of x" (number of symbols in x), and inf is the infimum over sets of real numbers. If w=v, they have no longest finite prefix, and d(w,v)=0; it can be shown that d satisfies all the other necessary properties of a metric.

Important subclasses

The most widely-used subclass of the ω-languages is the set of ω-regular languages, which enjoy the useful property of being recognizable by Büchi automata; thus the decision problem of ω-regular language membership is decidable and fairly straightforward to compute.

Bibliography